package leetcode.lt100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

class Solution_49 {
	public List<List<String>> groupAnagrams(String[] strs) {

		List<List<String>> res = new ArrayList<List<String>>();

		int l = strs.length;

		// 获得排序后的字符串数组
		String[] newStrs = new String[l];
		for (int i = 0; i < l; i++) {
			newStrs[i] = sort(strs[i]);
		}

		// 根据排序后的字符串循环放到map里
		Map<String, List<String>> map = new HashMap<String, List<String>>();
		for (int i = 0; i < l; i++) {
			String s = newStrs[i];
			if (map.containsKey(s)) {
				map.get(s).add(strs[i]);
			} else {
				List<String> list = new ArrayList<>();
				list.add(strs[i]);
				map.put(s, list);
			}
		}

		Iterator<Entry<String, List<String>>> iter = map.entrySet().iterator();
		while (iter.hasNext()) {
			Entry<String, List<String>> entry = iter.next();
			res.add(entry.getValue());
		}

		return res;
	}

	String sort(String s) {
		char[] c = s.toCharArray();
		Arrays.sort(c);
		return new String(c);
	}
}